import ast
import sys
import time
import multiprocessing
from collections import ChainMap
from deap import base, tools
from lbs_service import get_travel_time
from tools.lbs_utils import *

"""
将订单编号作为基因，手艺人作为种群
只做订单数量对等交换
1.优先选择路程时间不满足、2小时锁定时间的订单
2.交换时选择在附近的手艺人
3.缓存交换方案，不做重复搜索
4.取消交叉概率，改为完全执行
通过交换固定位置的订单编号，搜索更优解
种群基因形式(首位为手艺人编号，-1代表不可用时间)：
[1, -1, 0, 157, 157, 157, 157, 157, 0, 412, 412, 412, 412, 412, 0, 640, 640, 640, 640, 640, 0, 908, 908, 908, 908, 0]
[53, 0, 0, 164, 164, 164, 164, 0, 0, 418, 418, 418, 418, 0, 0, 646, 646, 646, 646, 0, 0, 0, 0, 0, 0, -1]
抽取手艺人的开放时间，需要对关闭时间做检查和限制
（去掉关闭和不可用时间）
目前测试发现订单未发生交换，订单交换还存在问题
"""
logging.basicConfig(level=logging.DEBUG, format='%(asctime)s - %(name)s - %(levelname)s - %(lineno)d: %(message)s')
# 不起作用
# logging.getLogger("requests.packages.urllib3.connectionpool").setLevel(logging.WARNING)
logger = logging.getLogger(__name__)
searched_solutions = []
travel_time_error_orders = []
travel_time_2hour_orders = None
travel_time_select_orders = None
travel_time_used_orders = None
offspring_neighbors = []
orders_travel_lock = {}
orders_delay_lock = {}
conn = None
df_artisans = None
df_orders = None
not_changeable_orders = None


def create_conn():
    global conn
    if conn is None:
        conn = conn_pgsql()


create_conn()


def get_yesterday(diff_days=1):
    today = datetime.date.today()
    one_day = datetime.timedelta(days=diff_days)
    ret_day = today - one_day
    return ret_day.strftime("%Y-%m-%d")


def load_data(a_day, city_id=0, cate_id=0):
    global df_artisans, df_orders, orders_travel_lock, orders_delay_lock, not_changeable_orders
    try:
        df_artisans = pd.read_csv('/data/disp/' + a_day + '/artisans_' + str(city_id) + '_' + str(cate_id) + '.csv')
        df_orders = pd.read_csv('/data/disp/' + a_day + '/orders_' + str(city_id) + '_' + str(cate_id) + '.csv')
    except:
        df_artisans = None
        df_orders = None
        logger.debug('no data file, stop')
    try:
        orders_travel_lock = dict(ChainMap(*df_artisans['travel_num'].apply(lambda x:ast.literal_eval(str(x)))))
        orders_delay_lock = dict(ChainMap(*df_artisans['delay_num'].apply(lambda x:ast.literal_eval(str(x)))))
    except Exception as e:
        logger.debug(e)
    # 排除非天猫渠道的订单
    try:
        not_changeable_orders = list(np.array(df_orders[(df_orders['out_channel'] != 1) & (df_orders['out_channel'] != 2)].index) + 1)
    except:
        not_changeable_orders = []


def create_artisan():
    gene = df_artisans['genes'].values
    return gene


def get_artisan_index(se):
    artisan_index = se['genes'][0]
    return artisan_index


class IndividualList(list):
    """
    可增加属性的 List
    """
    def __new__(self, *args, **kwargs):
        return super(IndividualList, self).__new__(self, args, kwargs)

    def __init__(self, *args, **kwargs):
        if len(args) == 1 and hasattr(args[0], '__iter__'):
            list.__init__(self, args[0])
        else:
            list.__init__(self, args)
        self.__dict__.update(kwargs)

    def __call__(self, **kwargs):
        self.__dict__.update(kwargs)
        return self


def check_travel_time(conn, individual):
    """
    检查路程时间是否有效
    :param conn:
    :param individual:
    :return:
    """
    global df_artisans, df_orders, travel_time_error_orders, orders_travel_lock, travel_time_2hour_orders
    error_routes = False
    artisan_orders = list(get_genes_order(individual))
    artisan_id = individual[0]
    total_time = 0
    long_time_orders = None
    for order_id in individual[1:]:
        if len(artisan_orders) > 0 and order_id > 0:
            pre_order = None
            now_order = None
            pre_order_index = artisan_orders.index(order_id)
            if pre_order_index > 0:
                pre_order_id = artisan_orders[pre_order_index - 1]
                pre_order = df_orders.iloc[pre_order_id - 1]
            else:
                # 如果是该手艺人第一单
                # logger.debug('artisan_id:' + str(artisan_id))
                if df_artisans is not None:
                    pre_order = df_artisans.iloc[artisan_id]
            if df_orders is not None:
                now_order = df_orders.iloc[order_id - 1]
            travel_time = 0
            if pre_order is not None:
                # 排除预约时间有冲突的情况
                try:
                    now_start = int(now_order['start'])
                except Exception as e:
                    logger.exception(e)
                    now_start = 0
                pre_time = pre_order['stop']
                if now_start < pre_time:
                    logger.debug('order[' + str(order_id) + '] service time ' + str(now_start) + ' < artisan[' + str(
                        artisan_id) + '] pre time ' + str(pre_time))
                    error_routes = True
                    break
                # 排除路程时间不够的情况
                try:
                    p1 = str(pre_order['lon']) + ',' + str(pre_order['lat'])
                    p2 = str(now_order['lon']) + ',' + str(now_order['lat'])
                    # 计算全天时间
                    start_hour = math.floor(now_order['start'] / (60 * 60) - 1)
                    if start_hour < 0:
                        start_hour = 0
                    start = str(start_hour) + ":00"
                    interval_time = int(now_order['start']) - int(pre_order['stop'])
                    travel_time = get_travel_time(conn, now_order['city_id'], p1, p2, start)
                    logger.debug('get travel_time: ' + str(travel_time))
                except Exception as e:
                    logger.debug('get travel_time error:')
                    logger.exception(e)
                    travel_time = 0
                if travel_time > interval_time:
                    logger.debug(
                        'order[' + str(order_id) + '] interval time ' + str(interval_time) + ' < artisan[' + str(
                            artisan_id) + '] travel time ' + str(travel_time))
                    error_routes = True
                    break
                orders_travel_lock[order_id] = math.ceil(travel_time / 60 * 30)
                # 由于新规则取消了2小时，放宽限制，将2小时改为1小时，超过半小时即锁定1小时
                # if travel_time > 60 * 30:
                if long_time_orders is not None:
                    df_row = pd.Series(data={'order_id': order_id, 'travel_time': travel_time})
                    long_time_orders = long_time_orders.append(df_row, ignore_index=True)
                else:
                    new_row = {'order_id': [order_id], 'travel_time': [travel_time]}
                    long_time_orders = pd.DataFrame.from_dict(new_row)
                # logger.debug(long_time_orders)
            total_time += travel_time
    if long_time_orders is not None and len(long_time_orders) > 0:
        long_time_orders['artisan_id'] = artisan_id
        logger.debug('find long travel time order num: ' + str(len(long_time_orders)))
        if travel_time_2hour_orders is not None:
            travel_time_2hour_orders = travel_time_2hour_orders.append(long_time_orders, ignore_index=True)
        else:
            travel_time_2hour_orders = long_time_orders
        # logger.debug(travel_time_2hour_orders)
        travel_time_2hour_orders.drop_duplicates('order_id', inplace=True)
    if error_routes:
        travel_time_error_orders.append(individual)
    return error_routes, total_time


def time_utilization(conn, individual):
    """
    评价个体的好坏，可观察该个体的时间利用率
    路程时间利用率 = 订单数量/路程时间
    交叉和突变时也要检查
    :param conn:
    :param individual:
    :return:
    """
    # logger.debug('gene: ' + str(individual))
    # 检查时间窗口是否满足
    error_routes, total_time = check_travel_time(conn, individual)
    order_nums = len(set([x for x in individual[1:] if int(x) > 0]))
    if error_routes:
        # 不管路线是否有效，应返回订单数
        return 0, order_nums, total_time
    if total_time > 0:
        utilization = order_nums / total_time
    else:
        utilization = 0
    return utilization, order_nums, total_time


def eval_vrptw(individual):
    """
    进化过程评价
    :param individual: 个体对象
    :param instance: 个体相关数据
    :return:
    """
    global conn
    conn.dispose()
    usage, order_num, total_time = time_utilization(conn, individual)
    return [usage, order_num, total_time]


class IndividualFitness(base.Fitness):
    weights = (1,)

    def __init__(self, *args, **kwargs):
        base.Fitness.__init__(self, *args, **kwargs)


def create_individual(list_str):
    try:
        x = ast.literal_eval(list_str)
    except:
        x = list(list_str)
    fitness, order_num, travel_time = eval_vrptw(x)
    genes = IndividualList(x, fitness=IndividualFitness(values=(fitness,)), order_num=order_num,
                           travel_time=travel_time)
    return genes


def create_artisans(n):
    global df_artisans
    genes = df_artisans['genes'].values[:n]
    return genes


def get_order_individual(order_id, individuals):
    """
    取得订单对应的个体
    :param order_id:
    :param individuals:
    :return:
    """
    order_ind = []
    for ind in individuals:
        if order_id in ind[1:]:
            order_ind = ind
            break
    return order_ind


def get_inventory_range(inventory, order_index):
    """
    取得订单在库存中的空闲时间范围
    :param inventory: 时间库存
    :param order_index: 订单索引位置
    :return:
    """
    try:
        lock_value = inventory[order_index]
    except:
        lock_value = -1
    if lock_value != 1:
        return -1, -1
    forward_rest_invent = inventory[:order_index]
    forward_order_length = get_prev_point(forward_rest_invent, [0, -1])
    try:
        forward_invent = forward_rest_invent[:len(forward_rest_invent) - forward_order_length]
    except:
        forward_invent = []
    back_rest_invent = inventory[order_index:]
    back_order_length = get_next_point(back_rest_invent, [0, -1])
    try:
        backward_invent = back_rest_invent[back_order_length:]
    except:
        backward_invent = []
    min_start_point = get_prev_point(forward_invent, [1, -1])
    min_start = len(forward_invent) - min_start_point
    if min_start < 0:
        min_start = 0
    max_end_point = get_next_point(backward_invent, [1, -1])
    if max_end_point < 0:
        max_end_point = 0
    max_end = max_end_point + order_index + back_order_length
    return min_start, max_end


def check_near_orders_range(se, start_time, stop_time):
    """
    检查附近订单的时间范围(由于individual变化，相应的genes也需要作出变化)
    :param se:
    :param start_time:
    :param stop_time:
    :return:
    """
    global df_artisans
    ind = []
    order_artisans = df_artisans[df_artisans['artisan_id'] == se['artisan_id']]
    if len(order_artisans) > 0:
        order_artisan= order_artisans.iloc[0]
        order_inventory = ast.literal_eval(order_artisan['inventory'])
        ind = list(ast.literal_eval(str(order_artisan['genes'])))
    # logger.debug(ind)
    try:
        near_order_index = ind.index(se['id']) - 1
    except:
        return False
    start_index, end_index = get_inventory_range(order_inventory, near_order_index)
    if start_time >= start_index * 30 * 60 and stop_time <= end_index * 30 * 60:
        return True
    else:
        return False


def gen_near_inds(individuals, select_offset):
    """
    生成就近个体特征
    :param individuals:
    :param select_offset:
    :return:
    """
    global travel_time_select_orders
    near_inds = {}
    used_artisans = []
    used_orders = []
    for ind in individuals:
        # 查找附近
        # 1.查看附近订单
        # 2.附近订单时间是否符合
        # 3.查看附近是否有手艺人
        artisan_id = ind[0]
        # 就近应与源订单匹配
        nearest_ind = []
        try:
            order_ids = travel_time_select_orders[travel_time_select_orders['artisan_id'] == artisan_id]['order_id'].values
        except:
            order_ids = []
        # logger.debug('get order_ids:' + str(order_ids))
        try:
            artisan = df_artisans.iloc[artisan_id]
        except:
            artisan = None
        # logger.debug('get artisan:' + str(artisan.name))
        artisan_inventory = ast.literal_eval(artisan['inventory'])
        order_list = get_genes_order(ind)
        # logger.debug('get individual orders:' + str(list(order_list)))
        for k, o in enumerate(order_list):
            if o in order_ids:
                now_order = df_orders.iloc[o - 1]
                # 如果在时间范围内只有1单，则可以交换 ?
                order_index = ind.index(o) - 1
                start_index, end_index = get_inventory_range(artisan_inventory, order_index)
                # logger.debug('order range:' + str(start_index * 30 * 60) + ' - ' + str(end_index * 30 * 60))
                near_orders = df_orders[
                    (df_orders['start'] >= start_index * 30 * 60) & (df_orders['stop'] <= end_index * 30 * 60)]
                # logger.debug('order time filter')
                # logger.debug(near_orders)
                if len(near_orders) > 0:
                    in_range_orders = near_orders.apply(check_near_orders_range, axis=1, start_time=now_order['start'],
                                                        stop_time=now_order['stop'])
                    near_orders = near_orders[in_range_orders]
                    # logger.debug('near_orders time filter')
                    # logger.debug(near_orders)
                    # 排除重复订单
                    near_orders = near_orders[
                        (~near_orders['id'].isin(order_list)) & (~near_orders['id'].isin(used_orders))]
                    # logger.debug('used order filter')
                    # logger.debug(near_orders)
                    if len(near_orders) > 0:
                        # 取得距离
                        near_orders['distance'] = near_orders.apply(get_distance, axis=1, order2=now_order)
                        near_orders.sort_values('distance', inplace=True)
                        # 查找对应individual，选择距离最近的1个订单作为候选订单
                        select_offset = min(len(near_orders) - 1, select_offset)
                        nearest_order = near_orders.iloc[select_offset]['id']
                        # logger.debug('find nearest order: ' + str(nearest_order))
                        nearest_ind = get_order_individual(nearest_order, individuals)
                        used_orders.append(order_list)
        # 删除空值\重复值
        if len(nearest_ind) > 0 and artisan_id not in used_artisans:
            artisan_ind = {artisan_id: nearest_ind}
            used_artisans.append(artisan_id)
            near_inds.update(artisan_ind)
    # return sorted(near_inds)
    return near_inds


def select_nearest_artisan(individuals):
    """
    选择附近的手艺人（作为交换）
    :param individuals:
    :return:
    """
    global df_orders, offspring_neighbors
    # logger.debug('select near artisan from:')
    # logger.debug(individuals)
    select_offset = 0
    near_inds = gen_near_inds(individuals, select_offset)
    while near_inds in offspring_neighbors and select_offset < len(individuals):
        near_inds = gen_near_inds(individuals, select_offset)
        # logger.debug('try find near inds in ' + str(select_offset) + ' times')
        select_offset += 1
    if len(near_inds) > 0 and near_inds not in offspring_neighbors:
        offspring_neighbors.append(near_inds)
    # logger.debug('offspring_neighbors:')
    # logger.debug(offspring_neighbors)
    logger.debug('get near inds:')
    logger.debug(near_inds)
    return near_inds


def get_inds_from_neighbors(inds, neighbor_inds):
    """
    根据近邻筛选个体(求交集)
    :param inds:
    :param neighbor_inds: 近邻基因，首位多出源个体ID
    :return:
    """
    neighbor_artisans = set(neighbor_inds.keys())
    ind_artisans = set(ind[0] for ind in inds)
    used_artisans = list(neighbor_artisans.intersection(ind_artisans))
    new_inds = []
    new_neighbor = []
    for artisan_id in used_artisans:
        for ind in inds:
            if artisan_id == ind[0]:
                new_inds.append(ind)
                break
        for n_key, n_ind in neighbor_inds.items():
            if artisan_id == n_key:
                new_neighbor.append(n_ind)
                break
    return new_inds, new_neighbor


def select_lock_2_hours(individuals, k):
    """
    优先选择锁定路程时间2小时的出行方案
    :param individuals:
    :param k:
    :return:
    """
    global travel_time_2hour_orders, travel_time_select_orders, travel_time_used_orders
    try:
        travel_time_2hour_orders.sort_values('travel_time', inplace=True, ascending=False)
        if travel_time_used_orders is None:
            travel_time_select_orders = travel_time_2hour_orders
        else:
            travel_time_select_orders = travel_time_2hour_orders[~travel_time_2hour_orders.index.isin(travel_time_used_orders.index)]
        sel_error_num = min(len(travel_time_select_orders), k)
    except:
        travel_time_select_orders = travel_time_2hour_orders
        travel_time_used_orders = travel_time_select_orders
        sel_error_num = k
    error_artisan_ids = []
    # 已经循环完所有订单时
    if sel_error_num == 0:
        travel_time_2hour_orders = None
        travel_time_select_orders = None
        travel_time_used_orders = None
    else:
        try:
            travel_time_select_orders = travel_time_select_orders[:sel_error_num]
            if travel_time_used_orders is None:
                travel_time_used_orders = travel_time_select_orders
            else:
                travel_time_used_orders.append(travel_time_select_orders)
            error_artisan_ids = travel_time_select_orders['artisan_id'].values
        except:
            travel_time_select_orders = None
            travel_time_used_orders = None
    # logger.debug(error_inds)
    error_individuals = [i for i in individuals if i[0] in error_artisan_ids]
    # logger.debug(error_individuals)
    news_ids = []
    for id in error_individuals:
        if id not in news_ids:
            news_ids.append(id)
    # logger.debug('selected new order ids:')
    # logger.debug(news_ids)
    return sorted(news_ids)
    # df_orders = df_orders[df_orders['lock_time'] == 2]
    # df_artisans = df_artisans[df_artisans['artisan_id'].isin(df_orders['artisan_id'])]
    # logger.debug('load orders:' + str(len(df_orders)))
    # logger.debug('load artisans:' + str(len(df_artisans)))


def select_travel_time_worst(individuals, k):
    """
    优先选择路程时间有问题的出行方案
    选择订单数最差的情况（排除已尝试过的选择）
    :param: individual
    :param: k
    :return:
    """
    global travel_time_error_orders
    sel_error_num = min(len(travel_time_error_orders), k)
    error_inds = travel_time_error_orders[:sel_error_num]
    error_individuals = [i for i in individuals if i[0] in error_inds]
    sel_inds = tools.selWorst(individuals, max(k - sel_error_num, 0))
    sel_inds.extend(error_individuals)
    # 防止出现重复个体
    news_ids = []
    for id in sel_inds:
        if id not in news_ids:
            news_ids.append(id)
    travel_time_error_orders = []
    return sorted(news_ids)


def drop_duplicate(ind_list):
    distinct_list = []
    for i in ind_list:
        if i not in distinct_list:
            distinct_list.append(i)
    return distinct_list


def remove_dict_value(dic, v):
    new_dic = {k: d for k, d in dic.items() if d != v}
    return new_dic


def genes_to_align(ind1, ind2):
    """
    基因二次编码
    步骤：
     1.去掉同为0部分
     2.左遍历，尾对齐
     3.右遍历，首对齐
     4.去重并去除不合法项
    :param ind1:
    :param ind2:
    :return:
    """
    # 1.去掉同为0部分
    # [1, 1, 2, 0, 0, 3, 3, 7, 9, 0, 10, 10]
    # [4, 0, 5, 5, 6, 6, 0, 0, 8, 8, 8, 0]
    try:
        i1_align, i2_align = zip(*[(i1, i2) for i1, i2 in zip(ind1, ind2) if (i1 + i2) > 0])
        i1_align = list(i1_align)
        i2_align = list(i2_align)
    except Exception as e:
        logger.debug(e)
        i1_align = [0]
        i2_align = [0]
        return i1_align, i2_align
        # logger.debug(ind1)
        # logger.debug(ind2)
        # logger.exception(e)

    # 2.左遍历，尾对齐
    # [1,1,2,2,0,3,3,7,9,9,10,10]
    # [4,4,5,5,6,6,6,0,8,8,8,8]
    i1_pre_dna = 0
    i2_pre_dna = 0
    for i in range(len(i1_align)):
        if i1_align[i] == i1_pre_dna or i2_align[i] == i2_pre_dna:
            if i1_align[i] == 0:
                i1_align[i] = i1_pre_dna
            if i2_align[i] == 0:
                i2_align[i] = i2_pre_dna
        # print("i1_align[" + str(i) + "]=" + str(i1_align[i]) + " i1_pre_dna=" + str(i1_pre_dna))
        # print("i2_align[" + str(i) + "]=" + str(i2_align[i]) + " i2_pre_dna=" + str(i2_pre_dna))
        i1_pre_dna = i1_align[i]
        i2_pre_dna = i2_align[i]

    # 3.右遍历，首对齐
    # [1, 1, 2, 2, 3, 3, 3, 7, 9, 9, 10, 10]
    # [4, 4, 5, 5, 6, 6, 6, 0, 8, 8, 8, 8]
    i1_pre_dna = 0
    i2_pre_dna = 0
    for i in range(len(i1_align) - 1, -1, -1):
        if i1_align[i] == i1_pre_dna or i2_align[i] == i2_pre_dna:
            if i1_align[i] == 0:
                i1_align[i] = i1_pre_dna
            if i2_align[i] == 0:
                i2_align[i] = i2_pre_dna
        i1_pre_dna = i1_align[i]
        i2_pre_dna = i2_align[i]

    # 4.去重并去除不合法项
    check_dict = {}
    duplicate_keys = []
    duplicate_values = []
    check_set = OrderedDict.fromkeys((i1, i2) for i1, i2 in zip(i1_align, i2_align)).keys()
    for o in list(check_set):
        if o[0] * o[1] != 0:
            # print(o[0], o[1])
            # 如果键已存在，说明是1对多关系，删除
            if o[0] in check_dict.keys():
                duplicate_keys.append(o[0])
            # 如果值已存在，同上
            elif o[1] in check_dict.values():
                duplicate_values.append(o[1])
            check_dict[o[0]] = o[1]
    for d in duplicate_keys:
        try:
            del check_dict[d]
        except:
            pass
    for d in duplicate_values:
        check_dict = remove_dict_value(check_dict, d)
    return list(check_dict.keys()), list(check_dict.values())


def align_to_genes(aligned, no_work_index, order_index, order_hour):
    """
    二次编码解码
    :param aligned: [1, 2, 3]
    :param no_work_index: [0,1,2,3,24,25,45,46,47] 非工作时间
    :param order_index: {'1': 12, '2': 18, '3': 28}
    :param order_hour: {'1': 2, '2': 3, '3': 3}
    :return: [-1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, -1, -1, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1]
    """
    gens = []
    order_id = 0
    repeat = 0
    # 开始组装
    for half_hour in range(24 * 2):
        if half_hour in no_work_index:
            code = -1
        elif repeat > 0:
            code = order_id
            repeat -= 1
        else:
            code = 0
            # 取出当前时间段的订单
            orders = [k for k, v in order_index.items() if v == half_hour]
            if orders is not None and len(orders) > 0:
                for a in aligned:
                    if str(a) in orders:
                        repeat = order_hour[str(a)] - 1
                        order_id = int(a)
                        code = order_id
                        break
        gens.append(code)
    if len(gens) != 48:
        logger.debug('gen genes length:' + str(len(gens)))
        logger.debug(gens)
    return gens


def get_no_work_index(ind):
    """
    取得不可交换的关闭时间
    :param ind: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0, -1, -1, -1]
    :return: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 45, 46, 47]
    """
    try:
        no_work_index = [i for i, v in enumerate(ind) if v == -1]
    except:
        no_work_index = []
    return no_work_index


def get_work_index(ind1, ind2):
    """
    取得可交换的开放时间
    :param ind1: [4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0, -1, -1, -1]
    :param ind2: [6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 22, 22, 22, 0, 0, 0, 0, 0, 0, -1, -1]
    :return:
        [0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0]
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 22, 22, 22, 0, 0, 0, 0, 0]
    """
    global not_changeable_orders
    try:
        no_work_index = [i for i, v in enumerate(ind1) if v == -1 or ind2[i] == -1]
    except:
        no_work_index = []
    work_ind1 = [order_id for i, order_id in enumerate(ind1) if i not in no_work_index and order_id not in not_changeable_orders]
    work_ind2 = [order_id for i, order_id in enumerate(ind2) if i not in no_work_index and order_id not in not_changeable_orders]
    return work_ind1, work_ind2


def get_order_index(work_ind):
    """
    取得订单位置
    :param work_ind: [0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0]
    :return: {'33': 8, '20': 20}
    """
    o_index = {}
    if work_ind is not None:
        for i, order_id in enumerate(work_ind):
            if order_id > 0 and str(order_id) not in o_index.keys():
                o_index[str(order_id)] = i
    return o_index


def get_order_hour(work_ind):
    """
    取得订单长度
    :param work_ind: [0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0]
    :return: {'33': 2, '20': 2}
    """
    o_hour = {}
    if work_ind is not None:
        o_hour = {str(order_id): work_ind.count(order_id) for i, order_id in enumerate(work_ind) if order_id > 0}
    return o_hour


def gen_inventory(ind, invent):
    """
    生成时间库存
    :param ind:  基因
    :param invent: 旧的时间库存
    :return:
    """
    global orders_travel_lock, orders_delay_lock
    plans = ind[1:]
    new_invent = []
    repeat = 0
    for i in range(48):
        if invent[i] == -1:
            new_invent.append(-1)
        elif plans[i] > 0:
            new_invent.append(1)
            # 锁住订单前路程时间
            if plans[i] in orders_travel_lock.keys():
                travel_lock_hour = orders_travel_lock[plans[i]]
                for j in range(1, travel_lock_hour + 1):
                    try:
                        if new_invent[i-j] != -1:
                            new_invent[i-j] = 1
                    except:
                        # 会出现路程时间在关闭时间内 及 首单路程时间较长的情况
                        # 这两种情况属于合理范围，不作处理
                        pass
            if plans[i] in orders_delay_lock.keys():
                repeat = orders_delay_lock[plans[i]]
        elif plans[i] == 0 and repeat > 0:
            # 锁住订单后缓冲时间
            new_invent.append(1)
            repeat -= 1
        else:
            new_invent.append(0)
    return new_invent


def update_artisan(ind):
    """
    更新个体相关的手艺人属性
    :param ind:
    :return:
    """
    global df_artisans
    artisan_index = ind[0]
    try:
        artisan = df_artisans.iloc[artisan_index]
    except:
        logger.warning('artisan[' + str(artisan_index) + '] not found')
        # return False
    artisan['genes'] = str(ind)
    artisan['inventory'] = str(gen_inventory(ind, artisan['inventory']))
    # df_artisans.update(artisan)


def change_item(ind1, ind2, index):
    new_ind1 = ind1.copy()
    new_ind2 = ind2.copy()
    new_ind1[index] = ind2[index]
    new_ind2[index] = ind1[index]
    return new_ind1, new_ind2


def order_time_matched(old_ind1, old_ind2, offset=0):
    """
    交叉方法 (排除不可交换订单)
    手艺人订单基因中的订单时间必须匹配，才能交换变异
    0.首先排除两个个体不可用时间
    目前只考虑1种可交换的情况：
    1.个体时间对应：个体1与个体2中的订单占用时间可交换
    原始基因：
    [100,-1,1,0,2,0,0,0,3,3,0,7,0,9,0,10,10]
    [104,-1,0,0,5,5,0,6,6,0,0,0,0,8,8,8,0]
    二次编码
    可用于交换变异的基因别名：
    [2,3]
    [5,6]
    :param old_ind1: [4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 20, 0, 0, -1, -1, -1]
    :param old_ind2: [6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 22, 22, 22, 0, 0, 0, 0, 0, 0, -1, -1]
    :param offset:
    :return:
    """
    # logger.debug('ind1: ' + str(len(ind1)) + ' ind2: ' + str(len(ind2)))
    # logger.debug(ind1)
    # logger.debug(ind2)
    ind1 = create_individual(old_ind1.copy())
    ind2 = create_individual(old_ind2.copy())
    genes1 = ind1[1:]
    genes2 = ind2[1:]
    if len(genes1) > 0 and len(genes2) > 0:
        no_work_index1 = get_no_work_index(genes1)
        no_work_index2 = get_no_work_index(genes2)
        work_ind1, work_ind2 = get_work_index(genes1, genes2)
        # 用字典记住订单的位置和长度，方便解码
        # logger.debug('work hours:')
        # logger.debug(work_ind1)
        # logger.debug(work_ind2)
        # 订单位置：order_index: {'1': 1, '2': 4, '3': 8}
        # 订单长度：order_hour: {'1': 2, '2': 1, '3': 2}
        # 记录不在交换工作区间内的订单
        order_index = get_order_index(genes1)
        no_order1 = list(order_index.keys())
        # logger.debug('order indexes:')
        # logger.debug(no_order1)
        order_index2 = get_order_index(genes2)
        no_order2 = list(order_index2.keys())
        # logger.debug(no_order2)
        order_index.update(order_index2)
        order_hour = get_order_hour(genes1)
        order_hour.update(get_order_hour(genes2))
        i1_aligned, i2_aligned = genes_to_align(work_ind1, work_ind2)
        if len(i1_aligned) >= 1 and len(i1_aligned) == len(i2_aligned):
            no_order1 = [int(o) for o in no_order1 if int(o) not in i1_aligned]
            no_order2 = [int(o) for o in no_order2 if int(o) not in i2_aligned]
            # logger.debug('no orders:')
            # logger.debug(no_order1)
            # logger.debug(no_order2)
            # logger.debug('old genes:')
            # logger.debug(i1_aligned)
            # logger.debug(i2_aligned)
            # 使用基因别名实现 均匀交叉（不会改变DNA位置）
            # ind_prob = 1 / len(i1_aligned)
            # i1, i2 = tools.cxUniform(i1_aligned, i2_aligned, ind_prob)
            # 确定性交叉
            if offset > len(i1_aligned) - 1:
                return False, False
            i1, i2 = change_item(i1_aligned, i2_aligned, offset)
            i1.extend(no_order1)
            i2.extend(no_order2)
            # logger.debug('genes mated:')
            # logger.debug(i1)
            # logger.debug(i2)
            # logger.debug('no_work_index1: ' + str(no_work_index1))
            # logger.debug('no_work_index2: ' + str(no_work_index2))
            # logger.debug('order_index: ' + str(order_index))
            # logger.debug('order_hour: ' + str(order_hour))
            ind1[1:] = align_to_genes(i1, no_work_index1, order_index, order_hour)
            ind2[1:] = align_to_genes(i2, no_work_index2, order_index, order_hour)
        # logger.debug('new gens:')
        # logger.debug(ind1)
        # logger.debug(ind2)
    # 交叉完毕后，更新对应的数据
    update_artisan(ind1)
    update_artisan(ind2)
    return ind1, ind2


def no_mutate(individual=None):
    # 将2小时订单记录在此清空，为下次进化准备
    global offspring_neighbors
    offspring_neighbors = []
    return individual


def cal_one_exchange(child1, child2, pop, toolbox, order_nums, offset=0):
    """
    单独计算1个订单交换的结果（确定性计算）
    :param child1:
    :param child2:
    :param pop:
    :param toolbox:
    :param order_nums:
    :param offset:
    :return:
    """
    now_fit = 0
    total_order_num = 0
    total_travel_time = 0
    choosed_inds = [child1, child2]
    choosed_order_num = sum([ind.order_num for ind in choosed_inds])
    # 保留未选择的父代个体，该写法会有遗漏，具体原因不明
    pre_pop = [x for x in pop if x not in choosed_inds]
    # logger.debug(choosed_inds)
    logger.debug('pre_pop order num: ' + str(sum([ind.order_num for ind in pre_pop])))
    new_child1, new_child2 = order_time_matched(child1, child2, offset)
    if new_child1 is False:
        return False, now_fit, total_order_num, total_travel_time
    # toolbox.mate(child1, child2)
    changed_inds = [new_child1, new_child2]
    # 排除交换失败的个体
    if [child1.copy(), child2.copy()] != changed_inds:
        new_solution = changed_inds.copy()
        new_solution.extend(pre_pop)
        new_solution = sorted(new_solution)
        if new_solution not in searched_solutions:
            searched_solutions.append(new_solution)
            good_solution = True
            fitnesses = map(toolbox.evaluate, changed_inds)
            valid_ind = []
            for ind, fit in zip(changed_inds, fitnesses):
                # 路程时间有问题时 fit=0
                if fit[0] == 0:
                    good_solution = False
                    logger.debug('find a error solution, break')
                    break
                ind.fitness.values = fit[0],
                ind.order_num = fit[1]
                ind.travel_time = fit[2]
                valid_ind.append(ind)
            valid_order_num = sum([ind.order_num for ind in valid_ind])
            logger.debug('valid_ind order num: ' + str(valid_order_num))
            # logger.debug(valid_ind)
            # 如果发现有 fitness 未填充，及订单数量错误，则否定该方案
            if len(changed_inds) != len(valid_ind) or choosed_order_num != valid_order_num:
                good_solution = False
            if good_solution:
                logger.debug("Evaluated " + str(len(valid_ind)) + " individuals")
                # The population is entirely replaced by the offspring
                tmp_pop = valid_ind.copy()
                tmp_pop.extend(pre_pop)
                # logger.debug('valid_ind length: ' + str(len(valid_ind)))
                logger.debug('pre_pop order num: ' + str(sum([ind.order_num for ind in pre_pop])))
                # 由于始终无法得知空fitness来源，在最终赋值前再次检查
                check_invalid = [ind for ind in tmp_pop if not ind.fitness.valid]
                if len(check_invalid) > 0:
                    logger.debug('fake good solution, drop it.')
                else:
                    pop = tmp_pop
                    # fit求和 无法保证总路程时间最小
                    # fits = [ind.fitness.values[0] for ind in pop]
                    total_order_num = sum([ind.order_num for ind in pop])
                    logger.debug('total_order_num: ' + str(total_order_num))
                    total_travel_time = sum([ind.travel_time for ind in pop])
                # 对丢单进行惩罚，不允许出现丢单和多单的现象
                if total_order_num != order_nums:
                    logger.debug('different order num error inds:')
                    logger.debug(choosed_inds)
                    logger.debug(changed_inds)
                    logger.debug(pre_pop)
                    now_fit = 0
                else:
                    # now_fit = sum(fits)
                    if total_travel_time > 0:
                        now_fit = total_order_num / total_travel_time
                    else:
                        now_fit = 0
                    logger.debug('Find a feasible solution, fitness: ' + str(now_fit))
                    logger.debug('artisans[' + str(len(pop)) + '], orders[' + str(total_order_num) + ']')
    return pop, now_fit, total_order_num, total_travel_time


def cal_one_offspring(toolbox, pop, new_offspring, new_neighbor, order_nums, off_index=0):
    """
    单独计算一代的结果（确定性计算）
    :param toolbox:
    :param pop:
    :param new_offspring:
    :param new_neighbor:
    :param order_nums:
    :param off_index:
    :return:
    """
    global searched_solutions
    logger.debug('order_nums: ' + str(order_nums))
    total_order_num = sum([ind.order_num for ind in pop])
    logger.debug('pop order num: ' + str(total_order_num))
    # 确定性交换，用于处理少量订单数据，注意 neighbor的 fitness 也要重新计算
    child1 = new_offspring[off_index]
    child2 = new_neighbor[off_index]
    better_fit = 0
    now_fit = 0
    total_travel_time = 0
    for i in range(min(len(child1), len(child2))):
        pop1, now_fit, total_order_num1, total_travel_time1 = cal_one_exchange(child1, child2, pop, toolbox, order_nums, i)
        if pop1 is False:
            break
        if better_fit < now_fit:
            better_fit = now_fit
            pop = pop1.copy()
            total_order_num = total_order_num1
            total_travel_time = total_travel_time1
            logger.debug("Find a better exchange, fitness: " + str(now_fit) + " , travel_time: " + str(total_travel_time))
    return pop, now_fit, total_order_num, total_travel_time


def ga_vrptw(pool_size, pop_size, gen_size, yesterday, better_limit=15, file_name='_0_0'):
    """
    遗传算法主程序
    :param pool_size: 线程池数量
    :param pop_size: 种群数量
    :param gen_size: 最多进化次数
    :param yesterday:
    :param better_limit: 最多派单次数
    :param file_name: 文件后缀
    :return:
    """
    global searched_solutions
    toolbox = base.Toolbox()
    if pool_size <= 0:
        pool = multiprocessing.Pool()
    else:
        pool = multiprocessing.Pool(pool_size)
    toolbox.register("map", pool.map)
    # 定义种群生成器
    # 不需要随机生成N个种群，只需要在现有固定接单手艺人的基础上交叉变异即可
    toolbox.register('population', create_artisans)
    # 生成种群
    pop = toolbox.population(n=pop_size)
    # 定义最小交叉概率(确保算法具备微调的能力)
    min_cx_pb = 1 / pop_size
    # 定义评价方法
    toolbox.register('evaluate', eval_vrptw)
    # 定义选择方法 每次选择最差配种（优先选择路程时间有问题的）
    # toolbox.register('select', tools.selWorst)
    # toolbox.register('select', select_travel_time_worst)
    toolbox.register('select', select_lock_2_hours)
    # 定义交叉方法
    toolbox.register('mate', order_time_matched)
    # 定义突变方法
    # 订单时间位置特殊，突变会导致时间窗口被破坏，不进行突变
    toolbox.register('mutate', no_mutate)
    # Begin the evolution
    start_time = time.time()
    g_total = 0  # 定义总迭代次数
    g_found = 0  # 定义优化次数
    g_one = 0  # 定义每轮迭代次数
    fitnesses = list(toolbox.map(toolbox.evaluate, pop))
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit[0],
        ind.order_num = fit[1]
        ind.travel_time = fit[2]
    # fits = [ind.fitness.values[0] for ind in pop]
    # best_fit = sum(fits)
    order_nums = sum([ind.order_num for ind in pop])
    logger.debug('start optimize: artisans[' + str(len(pop)) + '], orders[' + str(order_nums) + ']')
    total_order_nums = [order_nums]
    total_travel_time = sum([ind.travel_time for ind in pop])
    total_travel_times = [total_travel_time]
    if total_travel_time > 0:
        best_fit = order_nums / total_travel_time
    else:
        best_fit = 0
    best_fits = [best_fit]
    generations = [g_one]
    end_time = time.time()
    run_time = end_time - start_time
    run_times = [run_time]
    total_g_run_time = 0
    searched_solutions = [sorted(pop)]
    best_solution = []
    # 第一代种群中 未找到有效派单方案
    start_time = time.time()
    # 限制总迭代次数、优化次数、总迭代时间
    while g_total <= gen_size and g_found <= better_limit and total_g_run_time <= 60 * 60:
        # A new generation
        g_start_time = time.time()
        g_total += 1
        g_one += 1
        logger.debug("-- Generation %i -- Total Generation %i -- Found %i --" % (g_one, g_total, g_found))
        # Select the next generation individuals
        offspring = toolbox.select(pop, len(pop))
        # Clone the selected individuals
        offspring = list(map(toolbox.clone, offspring))
        # 选择与个体相近的候选位置
        offspring_neighbor = select_nearest_artisan(offspring)
        logger.debug("select " + str(len(offspring)) + " offspring")
        logger.debug("select " + str(len(offspring_neighbor)) + " neighbors")
        new_offspring, new_neighbor = get_inds_from_neighbors(offspring, offspring_neighbor)
        if len(new_offspring) == 0:
            logger.debug('no fitness neighbor found.')
            continue
        for off_index in range(len(new_offspring)):
            # 后代已经变化，通过更新pop体现
            # logger.debug('foreach off_index pop length: ' + str(len(pop)))
            pop1, now_fit, total_order_num, total_travel_time = cal_one_offspring(toolbox, pop, new_offspring, new_neighbor, order_nums, off_index)
            if (best_fit == 0 and g_found == 0) or best_fit < now_fit:
                best_fit = now_fit
                best_fits.append(best_fit)
                total_order_nums.append(total_order_num)
                total_travel_times.append(total_travel_time)
                generations.append(g_one)
                pop = pop1.copy()
                best_solution = pop
                logger.debug("Find a better solution, fitness: " + str(now_fit) + " , travel_time: " + str(total_travel_time))
                end_time = time.time()
                run_time = end_time - start_time
                run_times.append(run_time)
                start_time = time.time()
                g_found += 1
                g_one = 0
            # 为满足突变格式要求，随机选取一个individual，参数无实际用途
            no_mutate()
        g_end_time = time.time()
        total_g_run_time += (g_end_time - g_start_time)
    pool.close()
    logger.debug("Total Generation %i / %i -- Found %i / %i " % (g_total, gen_size, g_found, better_limit))
    logger.debug("-- End of (successful) evolution --")
    # 此处不同于传统的进化算法挑选个体
    # 而是挑选进化过程中得分最高的某一代
    if best_fit > 0:
        logger.debug("Best population is: ")
        logger.debug(best_solution)
        logger.debug(best_fit)
        best_df = pd.DataFrame({'genes': best_solution})
        if len(best_df) > 0:
            best_df['artisan_id'] = best_df.apply(get_artisan_index, axis=1)
            best_df.sort_values('artisan_id', inplace=True)
            best_df.to_csv('/data/disp/' + yesterday + '/result' + file_name + '.csv')
        eval_df = pd.DataFrame({'fits': best_fits, 'order_num': total_order_nums, 'travel_time': total_travel_times,
                                'generation': generations, 'run_time': run_times})
        eval_df.to_csv('/data/disp/' + yesterday + '/eval' + file_name + '.csv')


def train(yesterday, gen_size=100, better_limit=15, city_id='0', cate_id='0'):
    """
    进化主程序
    :param yesterday:
    :param gen_size:
    :param better_limit:
    :param city_id:
    :param cate_id:
    :return:
    """
    global df_artisans
    df_artisans['genes'] = df_artisans['genes'].apply(create_individual)
    pop_size = len(df_artisans)
    pool_size = math.ceil(pop_size / 2)
    file_tail_name = '_' + city_id + '_' + cate_id
    # Global creation of the individuals for GA
    ga_vrptw(
        pool_size=pool_size,
        pop_size=pop_size,
        gen_size=gen_size,
        yesterday=yesterday,
        better_limit=better_limit,
        file_name=file_tail_name
    )


if __name__ == '__main__':
    # 针对历史表现，只优化北京、上海 'tag_mei_rong', 'tag_mei_jia', 'tag_mei_jie'
    # 北京、上海、杭州、深圳
    # 'tag_mei_rong', 'tag_mei_jia', 'tag_mei_jie', 'tag_wei_zheng'
    try:
        city_id = int(sys.argv[1]) - 1
    except:
        city_id = 0
    try:
        cate_id = int(sys.argv[2]) - 1
    except:
        cate_id = 0
    try:
        day_interval = int(sys.argv[3])
    except:
        day_interval = 1
    if city_id < 0:
        city_id = 0
    if cate_id < 0:
        cate_id = 0
    if day_interval < 1:
        day_interval = 1
    yesterday = get_yesterday(day_interval)
    load_data(yesterday, city_id, cate_id)
    if df_artisans is not None:
        tic = time.process_time()
        train(yesterday, 30, 15, str(city_id), str(cate_id))
        logger.debug('Computing Time: %s' % (time.process_time() - tic))
